﻿// MyProject.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
//公众号：程序员速成 ，内含一辈子都让你感激自己的优质视频教程，欢迎关注

#include <iostream>
#include <map>
#include <stack>

#ifdef _DEBUG   //只在Debug（调试）模式下
#ifndef DEBUG_NEW
#define DEBUG_NEW new(_NORMAL_BLOCK,__FILE__,__LINE__) //重新定义new运算符
#define new DEBUG_NEW
#endif
#endif

//#include <boost/type_index.hpp>
using namespace std;
//#pragma warning(disable : 4996) 

namespace _nmsp1
{		
	//小表达式（节点）的父类
	class Expression
	{
	public:
		Expression(int num, char sign) :m_dgb_num(num), m_dbg_sign(sign) {} //构造函数
		virtual ~Expression() {} //做父类时析构函数应该为虚函数。

	public:
		//解析语法树中的当前节点
		virtual int interpret(map<char, int> var) = 0; //map容器中的键值对用于保存变量名以及对应的值

	public:
		//以下两个成员变量是为程序跟踪调试时观察某些数据方便而引入
		int m_dgb_num; //创建该对象时的一个编号，用于记录本对象是第几个创建。
		char m_dbg_sign; //标记本对象类型，可能是个字符v代表变量（终结符表达式），也可以是个是个加减号（非终结符表达式）
	};

	//变量表达式（终结符表达式）
	class VarExpression :public  Expression
	{
	public:
		VarExpression(const char &key,int num,char sign):Expression(num,sign)//构造函数
		{
			m_key = key;
		}

		virtual int interpret(map<char, int> var)
		{
			return var[m_key]; //返回变量名对应的数值
		}
	private:
		char m_key; //变量名，本范例中诸如a,b,c,d都是变量名
	};

	//运算符表达式（非终结符表达式）父类
	class SymbolExpression :public Expression
	{
	public:
		//构造函数
		SymbolExpression(Expression* left, Expression* right, int num, char sign) :m_left(left), m_right(right), Expression(num, sign) {}
		Expression* getLeft() { return m_left; }
		Expression* getRight() { return m_right; }

	protected:
		//左右各有一个操作数
		Expression* m_left;
		Expression* m_right;
	};

	//加法运算符表达式（非终结符表达式）
	class AddExpression :public SymbolExpression
	{
	public:
		//构造函数
		AddExpression(Expression* left, Expression* right, int num, char sign) : SymbolExpression(left,right,num, sign) {}
		virtual int interpret(map<char, int> var)
		{
			//把步骤拆开写，方便理解和观察
			int value1 = m_left->interpret(var); //递归调用左操作数的interpret方法
			int value2 = m_right->interpret(var); //递归调用右操作数的interpret方法
			int result = value1 + value2;
			return result; //返回两个变量相加的结果
		}
	};
	//减法运算符表达式（非终结符表达式）
	class SubExpression :public SymbolExpression
	{
	public:
		//构造函数
		SubExpression(Expression* left, Expression* right, int num, char sign) : SymbolExpression(left, right, num, sign) {}
		virtual int interpret(map<char, int> var)
		{
			//把步骤拆开写，方便理解和观察
			int value1 = m_left->interpret(var); //递归调用左操作数的interpret方法
			int value2 = m_right->interpret(var); //递归调用右操作数的interpret方法
			int result = value1 - value2;
			return result; //返回两个变量相减的结果
		}
	};
	//----------------------------
	//分析-创建语法树（表达式树）
	Expression* analyse(string strExp) //strExp：要计算结果的表达式字符串，比如"a-b+c+d"。
	{
		stack< Expression*> expStack; //这里用到了栈这种顺序容器
		Expression* left = nullptr;
		Expression* right = nullptr;
		int icount = 1;
		for (size_t i = 0; i < strExp.size(); ++i) //循环遍历表达式字符串中每个字符
		{
			switch (strExp[i])
			{
			case '+':
				//加法运算符表达式（非终结符表达式）
				left = expStack.top(); //返回栈顶元素，左操作数
				++i;
				right = new VarExpression(strExp[i], icount++, 'v'); //'v'代表变量节点
				//在栈顶增加元素
				expStack.push(new AddExpression(left, right, icount++, '+'));//'+'代表是个加法运算符节点
				break;
			case '-':
				//减法运算符表达式（非终结符表达式）
				left = expStack.top(); //返回栈顶元素
				++i;
				right = new VarExpression(strExp[i], icount++, 'v');
				expStack.push(new SubExpression(left, right, icount++, '-'));//'-'代表是个减法运算符节点
				break;
			default:
				//变量表达式（终结符表达式）
				expStack.push(new VarExpression(strExp[i], icount++, 'v'));
				break;
			} //end switch
		} //end for
		Expression* expression = expStack.top(); //返回栈顶元素
		return expression;
	}

	void release(Expression* expression)
	{
		//释放表达式树的节点内存
		SymbolExpression* pSe = dynamic_cast<SymbolExpression*>(expression); //此处代码有优化空间（不使用dynamic_cast），留给大家思考
		if (pSe)
		{
			release(pSe->getLeft());
			release(pSe->getRight());
		}
		delete expression;
	}

}

int main()
{
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);//程序退出时检测内存泄漏并显示到“输出”窗口
	
	//第21章 解释器（Interpreter）模式：解析器模式，行为型模式。适合对一些比较简单的文法结构进行分析（语言解释器）。
	//（1）一个用解释器模式编写的范例
	//一些变量，一个字母表示，a、b、c、d，值运行时指定。希望对这些变量进行加减法运算（不涉及乘除，考虑简单性）；
	//7、9、3、2，字符串“a-b+c+d”，“7-9+3+2” = 3; 
	//将这些规则表达为一个句子（实质就是如何将计算规则表达为一颗语法树【表达式树】），然后构建解释器来解释这个句子，这就是解释器模式所做的事。
	//非终结符表达式（树枝），终结符表达式（树叶）
	//语法树中的每个节点所属的类都会有一个叫做interpret的成员函数对本节点进行解释。


	string strExp = "a-b+c+d"; //将要求值的字符串表达式
	map<char, int> varmap;
	//下面是给字符串表达式中所有参与运算的变量一个对应的数值
	varmap.insert(make_pair('a', 7)); //类似于赋值语句a=7;
	varmap.insert(make_pair('b', 9)); //类似于赋值语句b=9;
	varmap.insert(make_pair('c', 3)); //类似于赋值语句c=3;
	varmap.insert(make_pair('d', 2)); //类似于赋值语句d=2;
	_nmsp1::Expression* expression = _nmsp1::analyse(strExp); //调用analyse函数创建语法树
	int result = expression->interpret(varmap);  //调用interpret接口求解字符串表达式的结果
	cout << "字符串表达式\"a-b+c+d\"的计算结果为：" << result << endl; //输出字符串表达式的结果

	_nmsp1::release(expression);

	return 0;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件

